/*
 * Copyright (c) 2012 Sean Connelly
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy of this software and
 * associated documentation files (the "Software"), to deal in the Software without restriction,
 * including without limitation the rights to use, copy, modify, merge, publish, distribute,
 * sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in all copies or
 * substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT
 * NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
 * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

//
// ubig is an unsigned integer only bound by memory, and serves as the base for big's and ratio's
//

var ubig_max = 65535;

function ubig_setDigit(a, digit, v) // a is an array, which should be modified
{
	if (v != 0)
	{
		while (a.length < digit)
			a.push(0);
		a[digit] = v;
	}
	else
	{
		if (digit < a.length - 1)
			a[digit] = 0;
		else if (digit == a.length - 1)
		{
			a.pop();
			while (a[a.length - 1] == 0)
				a.pop();
		}
	}
	return a;
}

function ubig_cmp(a, b) // a, b are arrays, returns -1, 0, 1
{
	if (a.length > b.length) // `this` has more digits
		return 1;
	if (a.length < b.length) // `r` has more digits
		return -1;
	for (var i = a.length - 1; i >= 0; i--)
	{
		if (a[i] > b[i])
			return 1;
		if (a[i] < b[i])
			return -1;
	}
	return 0;
}

function ubig_add(a, b) // a, b are arrays
{
	var max_len = a.length > b.length ? a.length : b.length;
	var carry = 0;
	var res;
	var out = [];
	for (var i = 0; i < max_len; i++)
	{
		res = carry;
		if (i < a.length)
			res += a[i];
		if (i < b.length)
			res += b[i];
		out.push(res % ubig_max);
		carry = Math.floor(res / ubig_max);
	}
	if (carry != 0)
		out.push(carry);
	return out;
}

function ubig_sub(a, b) // a, b are arrays, a is greater than b
{
	var borrow = 0;
	var out = [];
	for (var i = 0; i < a.length; i++)
	{
		var here = a[i] - borrow;
		if (i < b.length)
		{
			if (here < b[i])
			{
				borrow = 1;
				here += ubig_max;
			}
			else
				borrow = 0;
			here -= b[i];
		}
		else
		{
			if (here < 0)
			{
				borrow = 1;
				here += ubig_max;
			}
			else
				borrow = 0;
		}
		out.push(here);
	}
	while (out[out.length - 1] == 0)
		out.pop();
	return out;
}

function ubig_mul(a, b) // a, b are arrays
{
	if (a.length > b.length) // make `a` the shorter of the two, if possible
	{
		var t = a;
		a = b;
		b = t;
	}
	var res = [];
	var rowInit = [];
	for (var i = 0; i < a.length; i++)
	{
		var carry = 0;
		var row = rowInit.concat();
		rowInit.push(0);
		for (var j = 0; j < b.length; j++)
		{
			var n = a[i] * b[j] + carry;
			row.push(n % ubig_max);
			carry = Math.floor(n / ubig_max);
		}
		if (carry != 0)
			row.push(carry);
		res = ubig_add(res, row);
	}
	return res;
}

function ubig_divmod(a, b, wantMod) // a, b are arrays, b cannot be zero
{
	// if b is greater than a, then return 0, a
	if (b.length > a.length ||
		(b.length == a.length && b[b.length - 1] > a[a.length - 1]))
		return { div: [], mod: wantMod ? [].concat(a) : false };

	var buildQ = function(n, obj) {
			if (n <= 0)
				return obj;
			var obj2 = buildQ(Math.floor(n / 2), []);
			if (n % 2 == 1)
				obj.push(ubig_max - 1);
			return obj.concat(obj2, obj2);
		};
	var q = buildQ(a.length - b.length + 1, []);
	q.push(1);
	for (var digit_i = q.length - 1; digit_i >= 0; digit_i--)
	{
		var minVal = 0;
		var maxVal = q[digit_i];
		while (minVal < maxVal)
		{
			var midVal = Math.floor((minVal + maxVal) / 2);
			ubig_setDigit(q, digit_i, midVal);
			var cmp = ubig_cmp(ubig_mul(b, q), a);
			if (cmp == 0) // b * q == a, return q, 0
				return { div: q, mod: wantMod ? [] : false };
			else if (cmp > 0) // b * q > a
				maxVal = midVal;
			else // b * q < a
				minVal = midVal + 1;
		}
		ubig_setDigit(q, digit_i, maxVal);
	}
	q = ubig_sub(q, [1]); // subtract 1 from q
	return { div: q, mod: wantMod ? ubig_sub(a, ubig_mul(b, q)) : false };
}

function ubig_div(a, b) // a, b are arrays, b cannot be zero
{
	return ubig_divmod(a, b, false).div;
}

function ubig_mod(a, b) // a, b are arrays, b cannot be zero
{
	return ubig_divmod(a, b, true).mod;
}

function ubig_pow(a, b) // a, b are arrays
{
	if (b.length == 0 || (b.length == 1 && b[0] == 1))
		return [].concat(a);
	var res = ubig_pow(a, ubig_div(b, [2]));
	if (b[0] % 2 == 1)
		return ubig_mul(a, ubig_mul(res, res));
	return ubig_mul(res, res);
}

function ubig_create(num_dig)
{
	return {
			_getDigits: function() {
					return num_dig;
				},
			copy: function(r) {
					num_dig = r._getDigits().concat();
					return this;
				},
			isZero: function() {
					return num_dig.length == 0;
				},
			isOne: function() {
					return num_dig.length == 1 && num_dig[0] == 1 && !this._n;
				},
			isOdd: function() {
					return num_dig.length > 0 && (num_dig[0] & 1) != 0;
				},
			isEven: function() {
					return !this.isOdd();
				},
			setInt: function(num) {
					num = Math.floor(num);
					if (num < 0)
						throw 'invalid number; cannot set to negative number';
					num_dig = [];
					while (num > 0)
					{
						num_dig.push(num % ubig_max);
						num = Math.floor(num / ubig_max);
					}
					return this;
				},
			num: function() {
					var ret = 0;
					for (var i = num_dig.length - 1; i >= 0; i--)
						ret = (ret * ubig_max) + num_dig[i];
					return ret;
				},
			cmp: function(r) {
					return ubig_cmp(num_dig, r._getDigits());
				},
			add: function(r) {
					if (r.isZero())
						return this;
					if (this.isZero())
						return this.copy(r);
					num_dig = ubig_add(num_dig, r._getDigits());
					return this;
				},
			addcyc: function(r, m) {
					// MYTODO: this
				},
			sub: function(r) {
					if (r.isZero())
						return this;
					var cmp = this.cmp(r);
					if (cmp < 0)
						throw 'invalid result; result of subtraction is negative';
					else if (cmp == 0)
						return this.setInt(0);
					num_dig = ubig_sub(num_dig, r._getDigits());
					return this;
				},
			subcyc: function(r, m) {
					// MYTODO: this
				},
			mul: function(r) {
					if (this.isZero() || r.isOne())
						return this;
					if (r.isZero())
						return this.setInt(0);
					if (this.isOne())
						return this.copy(r);
					num_dig = ubig_mul(num_dig, r._getDigits());
					return this;
				},
			mulcyc: function(r, m) {
					// MYTODO: this
				},
			div: function(r) {
					if (r.isZero())
						throw 'division by zero';
					if (this.isZero() || r.isOne())
						return this;
					num_dig = ubig_div(num_dig, r._getDigits());
					return this;
				},
			mod: function(r) {
					if (r.isZero())
						throw 'division by zero';
					var cmp = this.cmp(r);
					if (cmp < 0)
						return this;
					else if (cmp == 0)
						return this.setInt(0);
					num_dig = ubig_mod(num_dig, r._getDigits());
					return this;
				},
			divmod: function(r) { // does not modify `this`
					if (r.isZero())
						throw 'division by zero';
					if (this.isZero())
						return { div: ubig_createCopy(this), mod: ubig_createCopy(r) };
					if (r.isOne())
						return { div: ubig_createCopy(this), mod: ubig_createInt(0) };
					var res = ubig_divmod(num_dig, r._getDigits(), true);
					return {
							div: ubig_create(res.div),
							mod: ubig_create(res.mod)
						};
				},
			pow: function(r) {
					if (r.isZero())
						return this.setInt(1);
					if (this.isZero() || this.isOne() || r.isOne())
						return this;
					num_dig = ubig_pow(num_dig, r._getDigits());
					return this;
				},
			powcyc: function(r, m) {
					// MYTODO: this
				},
			gcd: function(r) { // does not modify `this`
					var a = ubig_createCopy(this);
					var t;
					while (!r.isZero())
					{
						t = ubig_createCopy(r);
						r = a.mod(r);
						a = t;
					}
					return a;
				},
			toString: function() { // assumes ubig_max >= 10
					if (this.isZero())
						return '0';
					var v = ubig_createCopy(this);
					var b10 = ubig_createInt(10);
					var out = '';
					while (!v.isZero())
					{
						var m = ubig_createCopy(v).mod(b10);
						out = (m._getDigits().length > 0 ? m._getDigits()[0] : '0') + out;
						v.div(b10);
					}
					return out;
				}
		};
};

function ubig_createCopy(num)
{
	return ubig_createInt(0).copy(num);
}

function ubig_createInt(num)
{
	var z = ubig_create([]); // create zero
	if (num != 0)
		z.setInt(num);
	return z;
}

function ubig_createBase(str, base)
{
	var idxSrc = '0123456789abcdefghijklmnopqrstuvwxyz';
	if (base < 2 || base > idxSrc.length)
		throw 'invalid base; must be between 2 and ' + idxSrc.length;
	var base_b = ubig_createInt(base);
	str = str.toLowerCase();
	var ret = ubig_createInt(0);
	for (var i = 0; i < str.length; i++)
	{
		var idx = idxSrc.indexOf(str.charAt(i));
		if (idx == -1 || idx >= base)
			throw 'invalid string';
		ret.mul(base_b).add(ubig_createInt(idx));
	}
	return ret;
}

function ubig_createDec(decStr)
{
	return ubig_createBase(decStr, 10);
}

exports.createCopy = ubig_createCopy;
exports.createInt = ubig_createInt;
exports.createBase = ubig_createBase;
exports.createDec = ubig_createDec;
